package bank;

import java.util.*;

public class _56Merge {
    public static int[][] merge(int[][] intervals) {
        //  对下方算法进行改进：调整排序算法的思路
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}
/**
 * 效率较低
 * class Solution {
 *     public static int[][] merge(int[][] intervals) {
 *         if (intervals.length <= 1){
 *             return intervals;
 *         }
 *         List<int[]> list = new LinkedList<>();
 *         for (int i = 0;i < intervals.length - 1;i++){
 *             int minIndex = i;
 *             for (int j = i;j < intervals.length;j++){
 *                 if (intervals[j][0] < intervals[minIndex][0]){
 *                     minIndex = j;
 *                 }
 *             }
 *             //  交换intervals[i] 和 intervals[minIndex]
 *             if (i != minIndex){
 *                 swapArr(intervals,i,minIndex);
 *             }
 *         }
 *         //  两个数组a[],b[]可以合并的充要条件是：(a[0]<=b[0] && a[1]>=b[0]) || (a[0]>=b[0] && a[0]<=b[1])
 *         for (int i = 0;i < intervals.length - 1;i++){
 *             if (canMerge(intervals[i],intervals[i+1])){
 *                 intervals[i+1][0] = Math.min(intervals[i][0],intervals[i+1][0]);
 *                 intervals[i+1][1] = Math.max(intervals[i][1],intervals[i+1][1]);
 *             }else {
 *                 list.add(intervals[i]);
 *             }
 *         }
 *         list.add(intervals[intervals.length-1]);
 *         int[][] res = new int[list.size()][2];
 *         for (int i = 0;i < list.size();i++){
 *             res[i] = Arrays.copyOf(list.get(i),2);
 *         }
 *         return res;
 *     }
 *
 *     private static void swapArr(int[][] intervals, int i, int minIndex) {
 *         int temp = intervals[i][0];
 *         intervals[i][0] = intervals[minIndex][0];
 *         intervals[minIndex][0] = temp;
 *
 *         temp = intervals[i][1];
 *         intervals[i][1] = intervals[minIndex][1];
 *         intervals[minIndex][1] = temp;
 *     }
 *
 *     private static boolean canMerge(int[] a, int[] b) {
 *         if (a[0] > b[1] || b[0] > a[1]){
 *             return false;
 *         }
 *         return true;
 *     }
 * }
 */

